---

RedBlackTree.hpp

Go to the documentation of this file.

///////////////////////////////////////////////////////////////////////////////
/// @file RedBlackTree.hpp
///
/// @brief Destiny3D Red/Black Tree Manager for Memory Manager
///
/// @author Lightning
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Oct 2002
/// @author Lightning
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#include "deGlobalTypes.hpp"
#include "deMemory_priv.hpp"

#ifndef REDBLACK_TREE_HPP
#define REDBLACK_TREE_HPP

//flags and defines for the flags for checking/setting them in the red/black tree node

//type of nodes for the red/black tree
#define REDBLACKNODE_FREE       0x0000
#define REDBLACKNODE_ALLOC      0x0001

//set a node free or alloc
#define SetNodeFree(Node) Node->Type = Node->Type & ~REDBLACKNODE_ALLOC;
#define SetNodeAlloc(Node) Node->Type = Node->Type | REDBLACKNODE_ALLOC;

//is a node free or alloc
#define IsNodeFree(Node) (!IsNodeAlloc(Node))
#define IsNodeAlloc(Node) (Node->Type & REDBLACKNODE_ALLOC)


//red or black node entry
#define REDBLACKNODE_BLACK      0x0000
#define REDBLACKNODE_RED        0x0002

//set a node black or red
#define SetNodeBlack(Node) Node->Type = Node->Type & ~REDBLACKNODE_RED;
#define SetNodeRed(Node) Node->Type = Node->Type | REDBLACKNODE_RED;

//is a node black or red
#define IsNodeBlack(Node) (!IsNodeRed(Node))
#define IsNodeRed(Node) (Node->Type & REDBLACKNODE_RED)


//define the common node data
typedef struct RedBlackNode
{
    DWORD                   Type;           //type of node (free/alloc/etc) and Color (Black/Red)
    struct RedBlackNode     *Left;          //node with a smaller size
    struct RedBlackNode     *Right;         //node with a larger size
    struct RedBlackNode     *Parent;        //the parent node

    struct RedBlackNode     *LinkedLeft;    //pointer to the node entry to the left of Ptr
    struct RedBlackNode     *LinkedRight;   //pointer to the node entry to the right of Ptr
                                            //note, the end points in the linked list end with RedBlackNULLNode
    
    DWORD                   Size;           //size of the memory space
    void *                  Ptr;            //pointer to the memory space

    union
    {
        void                *ExtraData;     //used for alloc nodes, pointer to extra data about the allocation
        struct RedBlackNode *Brother;       //used for free nodes, the brother entry of a node
    };
} RedBlackNode;

//export the redblack null node
extern RedBlackNode RedBlackNULLNode;

//information about the above structure
//The brother entry is only used for free blocks and points to the first node of the same size as the parent
//all Brother nodes use left/right to point to each other and Parent = NULL.
//LinkedLeft and LinkedRight are all the blocks (free and alloc) in order based on ptr
//Parent is set to &RedBlackNULLNode for the Root entry to distinguish from Brother nodes

//red/black tree functions

//insert and remove tree nodes
deBoolean InsertRedBlackTreeNodeAlloc(RedBlackNode **Root, RedBlackNode *AllocNode);
deBoolean InsertRedBlackTreeNodeFree(RedBlackNode **Root, RedBlackNode *FreeNode);
void DeleteRedBlackTreeNode(RedBlackNode **Root, RedBlackNode *Node);

//find a tree node
RedBlackNode *FindRedBlackTreeNodeAlloc(RedBlackNode *Root, void *Ptr);
RedBlackNode *FindClosestRedBlackTreeNodePtr(RedBlackNode *Root, void *Ptr);
RedBlackNode *FindRedBlackTreeNodeFree(RedBlackNode *Root, DWORD Size);

#endif

---